import java.util.*;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 27
 * Time: 18:08
 */
//牛客 按之字形顺序打印二叉树
public class Solution2 {
    //法一 官方推荐方法队列
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        Queue<TreeNode> queue = new ArrayDeque<>();//也可以用链表实现队列
        ArrayList<ArrayList<Integer>> arrayLists1 = new ArrayList<>();
        if(pRoot == null) return arrayLists1;//如果root==null则要这样返回
        queue.offer(pRoot);
        int flag = -1;
        while (!queue.isEmpty()) {
            ArrayList<Integer> arrayList2 = new ArrayList<>();
            int size = queue.size();
            while(size > 0) {
                TreeNode node = queue.poll();
                if(node.left != null) {//这个条件很重要
                    queue.offer(node.left);
                }
                if(node.right != null) {//这个条件很重要
                    queue.offer(node.right);
                }
                arrayList2.add(node.val);
                size--;
            }
            flag *= -1;//第一行flag为1不用反转
            if(flag == -1) {
                Collections.reverse(arrayList2);
            }
            arrayLists1.add(arrayList2);
        }
        return arrayLists1;
    }

    //法二 官方方法双栈
    public ArrayList<ArrayList<Integer>> Print1 (TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
        if(pRoot == null) return arrayList;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(pRoot);
        while (!s1.isEmpty() || !s2.isEmpty()) {
            ArrayList<Integer> temp = new ArrayList<>();
            while (!s1.isEmpty()) {
                TreeNode node = s1.pop();
                temp.add(node.val);
                if(node.left != null) {
                    s2.push(node.left);
                }
                if(node.right != null) {
                    s2.push(node.right);
                }
            }
            arrayList.add(new ArrayList<>(temp));
            temp.clear();
            while (!s2.isEmpty()) {
                TreeNode node = s2.pop();
                temp.add(node.val);
                if(node.right != null) {
                    s1.push(node.right);
                }
                if(node.left != null) {
                    s1.push(node.left);
                }
            }
            if(!temp.isEmpty()) {//这个条件一定要加，因为s2栈有可能为空。s1栈也有可能为空，但s1栈为空时刚好退出最外层的while循环不会造成结果错误
                arrayList.add(temp);
            }
        }
        return arrayList;
    }
}
